import java.util.*;
public class test {
    // leetcode 733.图像渲染
    class Solution {
        // 解法1. bfs(广度优先搜索 -> 层)
        public int[] dx = {0,0,1,-1};
        public int[] dy = {1,-1,0,0};
        //这里不像dfs,需要判断是否使用过
        //因为我们可以在层序遍历中直接修改值,这样下次也扫描不到上一个方块
        //public boolean[][] count;
        public int row;
        public int col;
        public int[][] floodFill1(int[][] image, int sr, int sc, int color) {
            int prev = image[sr][sc];
            //剪枝.优化
            //如果 起始点颜色 = 目标颜色,那么则不必进行上色工作
            if(prev == color){
                return image;
            }
            row = image.length;
            col = image[0].length;
            //用queue存储每一层里扫描到,并且需要修改的方格坐标
            Queue<int[]> queue = new LinkedList<>();
            queue.add(new int[]{sr,sc});
            while(!queue.isEmpty()){
                int[] t = queue.poll();
                int t0 = t[0];
                int t1 = t[1];
                image[t0][t1] = color;
                for(int i = 0;i < 4;i++){
                    int x = t0 + dx[i];
                    int y = t1 + dy[i];
                    // 1. 保证x和y都不越界
                    // 2. 保证此时的image[x][y]是起点颜色
                    if(x >= 0 && x < row && y >= 0 && y < col && image[x][y] == prev){
                        queue.add(new int[]{x,y});
                    }
                }
            }
            return image;
        }
        // 解法2. dfs(深度优先搜索)
        public int[][] nums;
        public int prev;
        public int color;
        //public int row;
        //public int col;
        public int[][] floodFill(int[][] image,int sr,int sc,int color){
            prev = image[sr][sc];
            this.color = color;
            //同上,简单的剪枝优化
            if(prev == color){
                return image;
            }
            row = image.length;
            col = image[0].length;
            nums = image;
            dfs(sr,sc);
            nums[sr][sc] = color;
            return nums;
        }
        public void dfs(int r,int c){
            nums[r][c] = color;
            for(int i = 0;i < 4;i++){
                int x = r + dx[i];
                int y = c + dy[i];
                // 1. 保证x和y都不越界
                // 2. 保证此时的image[x][y]是起点颜色
                if(x >= 0 && x < row && y >= 0 && y < col && nums[x][y] == prev){
                    dfs(x,y);
                }
            }
            return;
        }
    }
    // leetcode 200.岛屿数量
    class Solution {
        // 解法1. bfs(广度优先搜索 -> 层)
        public boolean[][] count;
        public char[][] nums;
        public Queue<int[]> queue;
        public int[] dx = {0,0,1,-1};
        public int[] dy = {1,-1,0,0};
        public int row;
        public int col;
        //用于记录岛屿数量
        public int num = 0;
        public int numIslands1(char[][] grid) {
            row = grid.length;
            col = grid[0].length;
            nums = grid;
            count = new boolean[row][col];
            queue = new LinkedList<>();
            for(int i = 0;i < row;i++){
                for(int j = 0;j < col;j++){
                    // 1. 该位置为陆地
                    // 2. 该位置的陆地并没有被划分到某个岛屿
                    if(grid[i][j] == '1' && !count[i][j]){
                        queue.add(new int[]{i,j});
                        count[i][j] = true;
                        num++;
                        bfs(i,j);
                    }
                }
            }
            return num;
        }
        public void bfs(int r,int c){
            while(!queue.isEmpty()){
                int[] t = queue.poll();
                r = t[0];
                c = t[1];
                for(int i = 0;i < 4;i++){
                    int x = r + dx[i];
                    int y = c + dy[i];
                    // 1. 确保x和y没有越界访问
                    // 2. 确保当前位置没有被标记过
                    // 3. 确保当前位置为陆地
                    if(x >= 0 && x < row && y >= 0 && y < col && !count[x][y] && nums[x][y] == '1'){
                        queue.add(new int[]{x,y});
                        count[x][y] = true;
                    }
                }
            }
        }
        // 解法2. dfs(深度优先遍历)
        // 需要的全局变量,除了上述bfs中的queue,其余都是需要的,这里就不重新写了
        public int numIslands(char[][] grid) {
            row = grid.length;
            col = grid[0].length;
            nums = grid;
            count = new boolean[row][col];
            for(int i = 0;i < row;i++){
                for(int j = 0;j < col;j++){
                    if(grid[i][j] == '1' && !count[i][j]){
                        count[i][j] = true;
                        num++;
                        dfs(i,j);
                    }
                }
            }
            return num;
        }
        public void dfs(int r,int c){
            for(int i = 0;i < 4;i++){
                int x = r + dx[i];
                int y = c + dy[i];
                if(x >= 0 && x < row && y >= 0 && y < col && nums[x][y] == '1' && !count[x][y]){
                    count[x][y] = true;
                    dfs(x,y);
                }
            }
        }
    }
}
